#include <vector>
#include <string>
#include <unordered_map>
using namespace std;
/*
 * @lc app=leetcode.cn id=187 lang=cpp
 *
 * [187] 重复的DNA序列
 */

// @lc code=start
class Solution {
public:

    // 连最简单的算法都没想到, 哭死了
    // vector<string> findRepeatedDnaSequences(string s) {
        
    //     unordered_map<string, int> mapper;
    //     vector<string> res;
    //     if (s.size() < 10) return res;
    //     for (int i = 0; i < s.size() - 9; i++) {
    //         string x = s.substr(i, 10);
    //         if (!mapper.count(x)) mapper.insert({x, 1});
    //         else if (mapper[x] == 1) {
    //             res.push_back(x);
    //             mapper[x]++;
    //         }
    //     }
    //     return res;
    // }


    // 玩的是位运算
    vector<string> findRepeatedDnaSequences(string s) {
        unordered_map<char, int> num{{'A', 0}, {'C', 1}, {'G', 2}, {'T', 3}};
        unordered_map<int, int> mapper;
        vector<string> res;
        if (s.size() < 10) return res;
        int x = 0;
        for (int i = 0; i < 9; i++) {
            x = (x << 2) | num[s[i]];
        }
        for (int i = 0; i < s.size() - 9; i++) {
            x = ((x << 2) | num[s[i + 9]]) & ((1 << 20) - 1);
            if (mapper[x] == 0) mapper[x]++;
            else if (mapper[x] == 1) {
                res.push_back(s.substr(i, 10));
                mapper[x]++;
            }
        }
        return res;
    }
};
// @lc code=end

